import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;

/**
 * @author LKQ
 * @date 2022/1/6 14:16
 * @description 动态规划，dp[i][j]代表第i层，第j个数最小和，dp[i][j] = min(dp[i-1][j-1], dp[i-1][j]) + triangle[i][j]
 */
public class Solution {
    public static void main(String[] args) {
        List<List<Integer>> triangle = new ArrayList<>();
        List<Integer> list1 = new ArrayList<>(Collections.singletonList(2));
        List<Integer> list2 = new ArrayList<>(Arrays.asList(3, 4));
        List<Integer> list3 = new ArrayList<>(Arrays.asList(6, 5 ,7));
        List<Integer> list4 = new ArrayList<>(Arrays.asList(4, 1, 8, 3));
        triangle.add(list1);
        triangle.add(list2);
        triangle.add(list3);
        triangle.add(list4);
        Solution solution = new Solution();
        solution.minimumTotal(triangle);
    }

    public int minimumTotal(List<List<Integer>> triangle) {
        int ans = 0, row = triangle.size();
        int first;
        for (int i = 0, j = 0; i < row; i++) {
            if (i == 0) {
                first = triangle.get(0).get(0);
            }else {
                first = Math.min(triangle.get(i).get(j), triangle.get(i).get(j+1));
                if (first != triangle.get(i).get(j)) {
                    j = j + 1;
                }
            }
            ans += first;
        }
        return ans;
    }
}
